This Application is related to the following Applications, which were filed of even date herewith:
(1) xe2x80x9cUsage Based Methods of Traversing and Displaying Generalized Graph Structures,xe2x80x9d by Ed H. Chi, et al., Ser. No. 09/062,341; and
(2) xe2x80x9cMethods for Interactive Visualization of Spreading Activation Using Time Tubes and Disk Trees,xe2x80x9d by Peter L. T. Pirolli, et al., Ser. No. 09/062,540.
1. Field of the Invention
The present invention is related to the field of displaying a related series of generalized graph structures. Specifically, the present invention is related to displaying changes over time of structure and parameters of a generalized graph structure, and the present invention is related to displaying relationships between the related series of graphs. The present invention addresses the problem of coherently displaying the changes in structure, content, and usage of World Wide Web pages of a web site.
2. Discussion of the Related Art
The World-Wide Web (xe2x80x9cwebxe2x80x9d) is perhaps the most important information access mechanism to be introduced to the general public in the 20th Century. As larger numbers of organizations rely on the Internet to distribute information to potential consumers and investors, they also realize its potential for distributing and organizing large volumes of data for later retrieval by employees and business partners. A company""s web site is rapidly becoming one of its most important business investments.
As an information repository, a web site generally receives a high amounts of usage. Web site usage patterns that are derived by monitoring the how the company""s employees use its web site enhance the companies understanding of its business activities. For example, monitoring what product literature the sales force is downloading may be a way to forecast sales. In short, traditional market analysis can be applied to this information resource.
Analysts are interested in not just how the web pages are used, but as well as the context under which they are placed, such as the linkage structure and the web page content. A web site is a dynamic structure, because its topology as evidenced by its linkage structure, the contents of its pages, and its usage changes continually. Analysts want to be able to analyze the evolving web site.
Because of analysts increasing desire to discover and understand users""access patterns, relationships between web page contents, and to efficiently structure web sites""topology, a need exists for a set of visualization tools which aid in the process of web site analysis.
The topology, content, or usage of a web site may be modeled at any given time as a generalized graph structure having various parameters associated with the various nodes and/or links. In order to enable effective cognitive processing of the changes over time in a web site, a need exists for displaying the change over time in a coherent manner to a web site designer, administrator, or analyst.
A conventional technique for understanding a graph structure is to display a representation of the links and nodes which constitute the graph structure. One view of the World Wide Web is that of a graph structure, with web pages representing nodes and hyperlinks representing the links between the nodes. The various pages which make up a web site frequently change over time in structure, usage, and content. The structure, usage, and content of the web pages in a web site at any given time may be modeled as a graph. An object of the present invention is to provide a method for displaying in a coherent manner the changes over time of a web site""s structure, usage, and content.
According to the present invention, time tubes are generated by a method of displaying a related series of graphs. Time tubes according to the present invention are especially well suited for use as a web site analysis tool. Although the usefulness of time tubes according to the methods of the present invention is illustrated using the example of web site analysis, the methods are applicable to all fields involving evolving graph structures. For example, telecommunication systems, physical transport systems, such as highways, trains, and the like, and manufacturing systems can all be modeled as graphs and analyzed using time tubes.
Time tubes illustrate changes in a graph that undergoes one or more transformations from one state to another. In the preferred embodiment, the transformations are displayed using the length of the cylindrical tube, filling the length of the time tube with planar slices which represent the data at various stages of the transformations. Time tubes may encode several dimensions of the transformations simultaneously by altering the representation of size, color, and layout among the planar slices which make up the time tube.
Examples of the transformations that time tubes can display include, but are not limited to, temporal, value-based, and spatial transformations. Temporal changes occur when web pages are added or deleted over time. Value-based changes include node colors, which may be used to encode a specific page""s usage parameter, as measured by its visitation rate. Spatial changes include the scaling of physical dimension as graphs expand or contract in size.
According to the present invention, the states of a graph at various times are represented as a series of related graphs. The same nodes may exist in some or all of the graphs. According to the preferred embodiment the method of displaying the related series of graphs, an inventory of all existing nodes is performed so as to generate a list of all nodes that have existed at any time. This inventory is used to produce a layout template in which each unique node is assigned a unique layout position. To produce each planar slice, the specific nodes which exist in the slice are placed at their respective positions assigned in the layout template. Then the planar slices are displayed.
In another aspect of the present invention, corresponding nodes in planar slices are linked, such as with translucent streamlines. In the preferred embodiment of the present invention, this linking is performed in response to a user selecting a node in a planar slice by placing his cursor over the selected node, such that the nodes in other planar slices corresponding to the user""s selected node are displayed. This linking also may be performed so as to show clustering of two or more nodes in one planar slice into a single node in an adjacent planar slice.
Furthermore, because a time tube is a cylindrical log, it can be rotated along its central axis to move specific nodes closer to the user""s viewpoint. Because time tubes exist in a three dimensional work space, the user can change his viewing perspective for time tube, such as zooming into or out of an area of interest.
These and other features and advantages of the present invention are apparent from the Figures as fully described in the Detailed Description of the Invention.